//
// Created by Rory on 2020/10/23.
//

#include <stdlib.h>
#include "string.h"

int SimpleStringMatch(StrP mainStr, StrP pattern){
    int i = 1;//指向主串
    int j = 1;//指向模式串
    while (i<=mainStr->size && j<=pattern->size){
        if(mainStr->str[i] == pattern->str[j]){
            i++;
            j++;
        }else{
            i = i - j + 2;
            j = 1;
        }
    }

    if(j > pattern->size){
        return i - pattern->size; //or: return i - (j-1);
    }

    return 0;
}

void GetNextArray(StrP pattern,char* next){
//    next[0]禁用
    next[1] = 0;
    int i = 1;//指向模式串中第i的个字符
    int j = 0;
    while (i < pattern->size){
        if(j==0 || pattern->str[i] == pattern->str[j]){
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];
        }
    }


}

int KMP(StrP mainStr, StrP pattern){
    char* next = malloc(sizeof(char)*pattern->size + 1);//一定要加1，因为next[0]禁用
    GetNextArray(pattern,next);

    int i = 1;//指向主串
    int j = 1;//指向模式串
    while (i<mainStr->size && j<pattern->size){
        if(j == 0 || mainStr->str[i] == pattern->str[j]){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }

    free(next);
    if(j > pattern->size){
        return i - pattern->size; //or: return i - (j-1);
    }
    return 0;
}

